﻿using System;
using System.Diagnostics;

namespace Snappy.Sharp
{
    public class SnappyCompressor
    {
        private const int LITERAL = 0;
        private const int BLOCK_LOG = 15;
        private const int BLOCK_SIZE = 1 << BLOCK_LOG;

        private const int INPUT_MARGIN_BYTES = 15;

        private const int MAX_HASH_TABLE_BITS = 14;
        private const int MAX_HASH_TABLE_SIZE = 1 << MAX_HASH_TABLE_BITS;

        private readonly Func<byte[], int, int, int, int> FindMatchLength;

        public SnappyCompressor() : this(Utilities.NativeIntPtrSize()) { }

        private SnappyCompressor(int intPtrBytes)
        {
            if (intPtrBytes == 4)
            {
                FindMatchLength = FindMatchLength32;
            }
            else if (intPtrBytes == 8)
            {
                FindMatchLength = FindMatchLength64;
            }
            else
            {
                FindMatchLength = FindMatchLengthBasic;
            }
        }

        public int MaxCompressedLength(int sourceLength)
        {
            return 32 + sourceLength + sourceLength / 6;
        }

        public int Compress(byte[] uncompressed, int uncompressedOffset, int uncompressedLength, byte[] compressed)
        {
            return Compress(uncompressed, uncompressedOffset, uncompressedLength, compressed, 0);
        }

        private int Compress(byte[] uncompressed, int uncompressedOffset, int uncompressedLength, byte[] compressed, int compressedOffset)
        {
            int compressedIndex = WriteUncomressedLength(compressed, compressedOffset, uncompressedLength);
            int headLength = compressedIndex - compressedOffset;
            return headLength + CompressInternal(uncompressed, uncompressedOffset, uncompressedLength, compressed, compressedIndex);
        }

        private int CompressInternal(byte[] uncompressed, int uncompressedOffset, int uncompressedLength, byte[] compressed, int compressedOffset)
        {
            int compressedIndex = compressedOffset;
            short[] hashTable = GetHashTable(uncompressedLength);

            for (int read = 0; read < uncompressedLength; read += BLOCK_SIZE)
            {
                Array.Clear(hashTable, 0, hashTable.Length);

                compressedIndex = CompressFragment(
                    uncompressed,
                    uncompressedOffset + read,
                    Math.Min(uncompressedLength - read, BLOCK_SIZE),
                    compressed,
                    compressedIndex,
                    hashTable);
            }
            return compressedIndex - compressedOffset;

        }

        private int CompressFragment(byte[] input, int inputOffset, int inputSize, byte[] output, int outputIndex, short[] hashTable)
        {
            int inputIndex = inputOffset;
            int shift = (int)(32 - Utilities.Log2Floor((uint)hashTable.Length));
            int inputEnd = inputOffset + inputSize;
            int baseInputIndex = inputIndex;
            int nextEmitIndex = inputIndex;

            if (inputSize >= INPUT_MARGIN_BYTES)
            {
                int ipLimit = inputOffset + inputSize - INPUT_MARGIN_BYTES;

                uint currentIndexBytes = Utilities.GetFourBytes(input, ++inputIndex);
                for (uint nextHash = Hash(currentIndexBytes, shift); ;)
                {
                    uint skip = 32;

                    int nextIp = inputIndex;
                    int candidate;
                    do
                    {
                        inputIndex = nextIp;
                        uint hash = nextHash;
                        nextIp = (int)(inputIndex + (skip++ >> 5));
                        if (nextIp > ipLimit)
                        {
                            goto emit_remainder;
                        }
                        currentIndexBytes = Utilities.GetFourBytes(input, nextIp);
                        nextHash = Hash(currentIndexBytes, shift);
                        candidate = baseInputIndex + hashTable[hash];

                        hashTable[hash] = (short)(inputIndex - baseInputIndex);
                    } while (Utilities.GetFourBytes(input, inputIndex) != Utilities.GetFourBytes(input, candidate));

                    outputIndex = EmitLiteral(output, outputIndex, input, nextEmitIndex, inputIndex - nextEmitIndex, true);

                    uint candidateBytes = 0;
                    int insertTail;

                    do
                    {
                        int baseIndex = inputIndex;
                        int matched = 4 + FindMatchLength(input, candidate + 4, inputIndex + 4, inputEnd);
                        inputIndex += matched;
                        int offset = baseIndex - candidate;
                        outputIndex = EmitCopy(output, outputIndex, offset, matched);
                        insertTail = inputIndex - 1;
                        nextEmitIndex = inputIndex;
                        if (inputIndex >= ipLimit)
                        {
                            goto emit_remainder;
                        }
                        uint prevHash = Hash(Utilities.GetFourBytes(input, insertTail), shift);
                        hashTable[prevHash] = (short)(inputIndex - baseInputIndex - 1);
                        uint curHash = Hash(Utilities.GetFourBytes(input, insertTail + 1), shift);
                        candidate = baseInputIndex + hashTable[curHash];
                        candidateBytes = Utilities.GetFourBytes(input, candidate);
                        hashTable[curHash] = (short)(inputIndex - baseInputIndex);
                    } while (Utilities.GetFourBytes(input, insertTail + 1) == candidateBytes);

                    nextHash = Hash(Utilities.GetFourBytes(input, insertTail + 2), shift);
                    ++inputIndex;
                }
            }

        emit_remainder:
            if (nextEmitIndex < inputEnd)
            {
                outputIndex = EmitLiteral(output, outputIndex, input, nextEmitIndex, inputEnd - nextEmitIndex, false);
            }

            return outputIndex;
        }

        private static int EmitCopyLessThan64(byte[] output, int outputIndex, int offset, int length)
        {
            if (length < 12 && offset < 2048)
            {
                int lenMinus4 = length - 4;
                output[outputIndex++] = (byte)(1 | lenMinus4 << 2 | offset >> 8 << 5);
                output[outputIndex++] = (byte)offset;
            }
            else
            {
                output[outputIndex++] = (byte)(2 | length - 1 << 2);
                output[outputIndex++] = (byte)offset;
                output[outputIndex++] = (byte)(offset >> 8);
            }
            return outputIndex;
        }

        private static int EmitCopy(byte[] compressed, int compressedIndex, int offset, int length)
        {
            while (length >= 68)
            {
                compressedIndex = EmitCopyLessThan64(compressed, compressedIndex, offset, 64);
                length -= 64;
            }

            if (length > 64)
            {
                compressedIndex = EmitCopyLessThan64(compressed, compressedIndex, offset, 60);
                length -= 60;
            }

            compressedIndex = EmitCopyLessThan64(compressed, compressedIndex, offset, length);
            return compressedIndex;
        }

        private static int FindMatchLengthBasic(byte[] s1, int s1Index, int s2Index, int s2Limit)
        {
            int matched = 0;
            while (s2Index + matched < s2Limit && s1[s1Index + matched] == s1[s2Index + matched])
            {
                ++matched;
            }
            return matched;
        }

        private static int FindMatchLength32(byte[] s1, int s1Index, int s2Index, int s2Limit)
        {
            int matched = 0;
            while (s2Index <= s2Limit - 4)
            {
                uint a = Utilities.GetFourBytes(s1, s2Index);
                uint b = Utilities.GetFourBytes(s1, s1Index + matched);

                if (a == b)
                {
                    s2Index += 4;
                    matched += 4;
                }
                else
                {
                    uint c = a ^ b;
                    int matchingBits = (int)Utilities.NumberOfTrailingZeros(c);
                    matched += matchingBits >> 3;
                    return matched;
                }
            }
            while (s2Index < s2Limit)
            {
                if (s1[s1Index + matched] == s1[s2Index])
                {
                    ++s2Index;
                    ++matched;
                }
                else
                {
                    return matched;
                }
            }
            return matched;
        }


        private static int FindMatchLength64(byte[] s1, int s1Index, int s2Index, int s2Limit)
        {
            int matched = 0;
            while (s2Index <= s2Limit - 8)
            {
                ulong a = Utilities.GetEightBytes(s1, s2Index);
                ulong b = Utilities.GetEightBytes(s1, s1Index + matched);

                if (a == b)
                {
                    s2Index += 8;
                    matched += 8;
                }
                else
                {
                    ulong c = a ^ b;
                    int matchingBits = (int)Utilities.NumberOfTrailingZeros(c);
                    matched += matchingBits >> 3;
                    return matched;
                }
            }
            while (s2Index < s2Limit)
            {
                if (s1[s1Index + matched] == s1[s2Index])
                {
                    ++s2Index;
                    ++matched;
                }
                else
                {
                    return matched;
                }
            }
            return matched;
        }


        private int EmitLiteral(byte[] output, int outputIndex, byte[] literal, int literalIndex, int length, bool allowFastPath)
        {
            int n = length - 1;
            outputIndex = EmitLiteralTag(output, outputIndex, n);
            if (allowFastPath && length <= 16)
            {
                Utilities.UnalignedCopy64(literal, literalIndex, output, outputIndex);
                Utilities.UnalignedCopy64(literal, literalIndex + 8, output, outputIndex + 8);
                return outputIndex + length;
            }
            Buffer.BlockCopy(literal, literalIndex, output, outputIndex, length);
            return outputIndex + length;
        }

        private int EmitLiteralTag(byte[] output, int outputIndex, int size)
        {
            if (size < 60)
            {
                output[outputIndex++] = (byte)(LITERAL | size << 2);
            }
            else
            {
                int baseIndex = outputIndex;
                outputIndex++;
                int count = 0;
                while (size > 0)
                {
                    output[outputIndex++] = (byte)(size & 0xff);
                    size >>= 8;
                    count++;
                }
                output[baseIndex] = (byte)(LITERAL | 59 + count << 2);
            }
            return outputIndex;
        }

        private static uint Hash(uint bytes, int shift)
        {
            const int kMul = 0x1e35a7bd;
            return bytes * kMul >> shift;
        }

        private int WriteUncomressedLength(byte[] compressed, int compressedOffset, int uncompressedLength)
        {
            const int bitMask = 0x80;
            if (uncompressedLength < 0)
                throw new ArgumentException("uncompressedLength");

            while (uncompressedLength >= bitMask)
            {
                compressed[compressedOffset++] = (byte)(uncompressedLength | bitMask);
                uncompressedLength = uncompressedLength >> 7;
            }
            compressed[compressedOffset++] = (byte)uncompressedLength;

            return compressedOffset;
        }

        private short[] GetHashTable(int inputLength)
        {
            int tableSize = 256;
            while (tableSize < MAX_HASH_TABLE_SIZE && tableSize < inputLength)
            {
                tableSize <<= 1;
            }
            return new short[tableSize];
        }
    }
}
